<head>
    <meta charset="UTF-8">
<title>算法训练 Figure Eight</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>【问题描述】</p>
<div>&nbsp;</div>
<div>Farmer John的奶牛最近收到一块大理石。但不幸的是，这块石头有些不完整。</div>
<div>为了说明这块石头的状况，我们就可以用一个N*N正方形网格（5 &lt;= N &lt;=300）来描述，</div>
<div>其中字符'*'代表石头的缺损部分，'.'表示石头完美无瑕的部分。</div>
<div>&nbsp;</div>
<div>奶牛要在这块大理石上雕刻一个数字&quot;8&quot;（自从奶牛们把它们的四只蹄子都劈开，可以方便地用它们的&quot;脚趾&quot;数出8以内的数，奶牛就十分喜爱数字8）。</div>
<div>然而，它们也需要你的帮助，以确定数字8在这块大理石上最佳的雕刻位置。这里有几个要求来定义一个有效的数字8：</div>
<div>&nbsp;</div>
<div>*数字8由上下两个矩形构成。</div>
<div>*数字8的上下两个矩形都满足至少有一个单元格在矩形内部。</div>
<div>*数字8顶部的矩形的底边必须为底部矩形顶边的子集。</div>
<div>*数字8只能刻在大理石完美无瑕的部分。</div>
<div>*规定数字8的得分为上矩形和下矩形的面积的乘积，它们希望得分能达到最大。</div>
<div>&nbsp;</div>
<div>例如，给出这样的一块大理石：</div>
<div style="text-align: center;"><img src="http://lx.lanqiao.cn/RequireFile.do?fid=R6Ahjnfe" width="178" height="310" alt="" /></div>
<div>&nbsp;</div>
<div>最优的8摆放位置如下图所示：</div>
<div style="text-align: center;"><img src="http://lx.lanqiao.cn/RequireFile.do?fid=AbR9RTJy" width="177" height="319" alt="" /></div>
<div>&nbsp;</div>
<div>上矩形的面积为6*9=54，而下矩形的面积则是12*6=72。所以，它的得分就是54*72=3888。</div>
<div>&nbsp;</div>
<p>【输入格式】</p>
<div>第一行包括一个整数N，代表大理石的边长。</div>
<div>第二到N+1行，每一行描述了大理石的一行，包含着N个字符，每一个字符是&quot;*&quot;（代表缺损的部分）与&quot;.&quot;（代表完美无瑕的部分）其中一个。</div>
<p>【输出格式】</p>
<div>第一行包含一个整数，代表符合条件数字8中最大的得分。若没有一个合法的数字8，请输出-1。</div>
<p>【样例输入】</p>
<div>15</div>
<div>...............</div>
<div>...............</div>
<div>...*******.....</div>
<div>.*....*.......*</div>
<div>.*......*....*.</div>
<div>....*..........</div>
<div>...*...****....</div>
<div>...............</div>
<div>..**.*..*..*...</div>
<div>...*...**.*....</div>
<div>*..*...*.......</div>
<div>...............</div>
<div>.....*..*......</div>
<div>.........*.....</div>
<div>...............</div>
<p>【样例输出】</p>
<div>3888</div>
<p>【数据规模和约定】</p>
<div>对于30%的数据，5&lt;=N&lt;=80。</div>
<div>对于100%的数据，5&lt;=N&lt;=300。</div>
<div>&nbsp;</div>